package newcoder_exp.bytedance;

import java.lang.reflect.Array;

import org.junit.Test;

import linked.ListNode;
import utils.ArrayGenerator;

public class Bd4 {
    
    //
    public ListNode sort(ListNode head) {
        if (head == null || head.next == null) return head;
        return divide(head);
    }

    public ListNode divide (ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode mid = findMiddle(head), temp = mid.next;
        mid.next = null;
        //head ~ mid的部分
        ListNode left = divide(head);
        //temp ~ tail的一部分
        ListNode right = divide(temp);

        return merge(left, right);
    }

    @Test
    public void test3() {
        ListNode h1 = ListNode.newListNodeFromArray(new int[]{1,21});
        ListNode h2 = ListNode.newListNodeFromArray(new int[]{1,21,3});
        ListNode h3 = ListNode.newListNodeFromArray(new int[]{1,21,3,4});
        ListNode h4 = ListNode.newListNodeFromArray(ArrayGenerator.getArray(30, 10));

        System.out.println(divide(h1));
        System.out.println(divide(h2));
        System.out.println(divide(h3));
        System.out.println(sort(h4));

    }

    public ListNode findMiddle(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode fast = head, slow = head, pre = null;
        while (true) {
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == null || fast.next == null) {
                return pre;
            }
        }
    }

    @Test
    public void test2() {
        ListNode h1 = ListNode.newListNodeFromArray(new int[]{1,2});
        ListNode h2 = ListNode.newListNodeFromArray(new int[]{1,2,3});
        ListNode h3 = ListNode.newListNodeFromArray(new int[]{1,2,3,4});

        System.out.println(findMiddle(h1));
        System.out.println(findMiddle(h2));
        System.out.println(findMiddle(h3));

    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode res = new ListNode(0), result = res;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                res.next = left;
                left = left.next;
            } else {
                res.next = right;
                right = right.next;
            }
            res = res.next;
        }
        if (left == null) left = right;
        res.next = left;
        return result.next;
    }

    @Test
    public void test1() {
        ListNode left = ListNode.newListNodeFromArray(new int[] {1, 3, 41, 2});
        ListNode right = ListNode.newListNodeFromArray(new int[] {2, 2, 31, 2});
        left = merge(left, right);
        System.out.println(left);
    }
}
